/**
 * @file xmem.c
 * @brief 
 * @author Gavin (420260138@qq.com)
 * @version 1.1
 * @date 2020-07-20
 * 
 * @copyright Copyright (c) {2020}  Gavin.Hsu
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of Apache License Version 2.0
 * 
 * @par 修改日志:
 * <table>
 * <tr><th>Date       <th>Version <th>Author  <th>Description
 * <tr><td>2020-07-20 <td>1.1     <td>Gavin     <td>update
 * </table>
 */
#include "xconfig.h"
#include "platform.h"
#include "xtypes.h"
#include "utilities.h"
#include "xmem.h"


#define XMEM_VER "1.1.0"

/***************************************************************************
                         X-Memory Physical Sketch
----------------------------------------------------------------------------
|                                  Pool                                    |
|                                                                          |
|    ------------------    --------------------    --------------------    |
|    |  SuperBlock    |    |       Block      |    |       Block      |    |
|    |                |    |                  |    |                  |    |
|    |  4-bytes list  |    |  xx-bytes block  |    |  xxx-bytes block |    |
|    |                |    |                  |    |                  |    |
|    ------------------    --------------------    --------------------    |
|                                                                          |
|    ------------------    --------------------    --------------------    |
|    |  SuperBlock    |    |       Block      |    |       Block      |    |
|    |                |    |                  |    |                  |    |
|    |  8-bytes list  |    | xxxx-bytes block |    | xxxxx-bytes block|    |
|    |                |    |                  |    |                  |    |
|    ------------------    --------------------    --------------------    |
|                                                                          |
|    ------------------                                                    |
|    |  SuperBlock    |                                                    |
|    |                |             ...                     ...            |
|    |  16-bytes list |                                                    |
|    |                |                                                    |
|    ------------------                                                    |
|                                                                          |
----------------------------------------------------------------------------
****************************************************************************/
#if XMEM_SUPERBLOCK_SUPPORT
static const xMemSuperBlockInitDesc xMemSuperBlockInitDescList[] = 
{
    #if XMEM_SUPERBLOCK_1CELL_CNT
    {XMEM_CELL_SIZE,XMEM_SUPERBLOCK_1CELL_CNT},
    #endif
    #if XMEM_SUPERBLOCK_2CELL_CNT
    {XMEM_2CELL_SIZE,XMEM_SUPERBLOCK_2CELL_CNT},
    #endif
    #if XMEM_SUPERBLOCK_4CELL_CNT
    {XMEM_4CELL_SIZE,XMEM_SUPERBLOCK_4CELL_CNT},
    #endif
    #if XMEM_SUPERBLOCK_8CELL_CNT
    {XMEM_8CELL_SIZE,XMEM_SUPERBLOCK_8CELL_CNT},
    #endif
};
static xMemSuperBlock * xMemSuperBlockList[] = 
{
    #if XMEM_SUPERBLOCK_1CELL_CNT
    NULL,
    #endif
    #if XMEM_SUPERBLOCK_2CELL_CNT
    NULL,
    #endif
    #if XMEM_SUPERBLOCK_4CELL_CNT
    NULL,
    #endif
    #if XMEM_SUPERBLOCK_8CELL_CNT
    NULL,
    #endif
};
#endif // end of XMEM_SUPERBLOCK_SUPPORT

static pxMemMgrHdr xMemMgrHdrList;
static pxMemBlock xMemBlkList = NULL;
static AddressType xMemMgrHdrListEnd = 0;
static AddressType xMemBlkPoolStart = 0;
static u8 xMemSuperBlkCellMax = 0;
static AddressType xMem_Addr = 0;
static size_t xMem_Size = 0;

#define XMEM_POOL_START (xMem_Addr)
#define XMEM_POOL_END (xMem_Addr+xMem_Size)



/**
 * @brief Init block list
 */
static void xMemBlockListInit( void )
{
    #if XMEM_HEADER_DIVIDE
    xMemBlkPoolStart = XMEM_POOL_END;
    xMemBlkList = NULL;
    #else
    xMemBlkList = (pxMemBlock)XMEM_POOL_START;
    xMemBlkList->blksize = xMem_Size-XMEM_BLOCK_SIZE;
    xMemBlkList->next = NULL;
    xMemBlkList->free = 1;    
    #endif// end of XMEM_HEADER_DIVIDE
}

#if XMEM_HEADER_DIVIDE
/**
 * @brief Init management header list
 */
static void xMemMgrHdrListInit( void )
{
    /*
      -------------------------------------------------------------------------------
      | Header List|  xMemHdrEnd--->|  ...   |<---xMemBlkStart  |Blocks,Super Blocks|
      -------------------------------------------------------------------------------
      This Structure avoid Header List overwrote by pointer which allocated from X-Memory Pool
     */
    xMemMgrHdrList = NULL;
    xMemMgrHdrListEnd = XMEM_POOL_START;
}

/**
 * @brief  Get a header
 * @param  type             Header Type
 * @param  size             Header Size
 * @return void* NULL-failure, other- Header address
 */
static void * xMemMgrHdrGet( u8 type, size_t size )
{
    pxMemMgrHdr hdr = NULL, hdrnew = NULL, hdrprev = NULL;

    /*
     -------------------------------------------
     |  ...  |  prev  |  blk  |  next  |  ...  |
     -------------------------------------------
    */

    hdr = xMemMgrHdrList;

    while( hdr )
    {
        if( hdr->type == XMEM_LIST_TYPE_FREE )
        {
            if( hdr->size >= size + XMEM_HEADER_SIZE )
            {
                //split into 2 headers
                hdrnew = ( pxMemMgrHdr )( ( void* )( ( AddressType ) hdr + size + XMEM_HEADER_SIZE) );
                hdrnew->type = XMEM_LIST_TYPE_FREE;
                hdrnew->size = hdr->size - size - XMEM_HEADER_SIZE;
                hdrnew->next = hdr->next;
                hdr->next = hdrnew;
                hdr->size = size;
                hdr->type = type;
                return (void*)( (AddressType ) hdr + XMEM_HEADER_SIZE );                    
            }
            else if( hdr->size >= size )
            {
                //most fitable, block size equals to required size
                hdr->type = type;
                return ( void* )( ( AddressType ) hdr + XMEM_HEADER_SIZE );
            }
        }
        hdrprev = hdr;
        hdr = hdr->next;
    }

    if( xMemMgrHdrListEnd + size + XMEM_HEADER_SIZE < xMemBlkPoolStart )
    {
        hdrnew = ( pxMemMgrHdr ) xMemMgrHdrListEnd;
        if( hdrprev )
        {
            hdrprev->next = hdrnew;
        }
        else
        {
            xMemMgrHdrList = hdrnew;
        }
        hdrnew->next = NULL;
        hdrnew->size = size;
        hdrnew->type = type;
        xMemMgrHdrListEnd += size + XMEM_HEADER_SIZE;
        hdr = hdrnew;
        return ( void* )( ( AddressType ) hdr + XMEM_HEADER_SIZE );
    }

    return NULL;
}

/**
 * @brief Put a Header
 * @param  header           header to put
 */
static void xMemMgrHdrPut( void * header )
{
    pxMemMgrHdr hdrfree = NULL, hdrprev = NULL, hdrprev2 = NULL;

    /*
     -------------------------------------------
     |  ...  |  prev  |  blk  |  next  |  ...  |
     -------------------------------------------
    */

    hdrfree = xMemMgrHdrList;
    while( hdrfree )
    {
        if( ( AddressType ) hdrfree + XMEM_HEADER_SIZE == ( AddressType ) header )
        {
            xMemAssert( hdrfree->type != XMEM_LIST_TYPE_FREE );

            hdrfree->type = XMEM_LIST_TYPE_FREE;
            if( hdrprev && hdrprev->type == XMEM_LIST_TYPE_FREE )
            {
                hdrprev->next = hdrfree->next;
                hdrprev->size += hdrfree->size + XMEM_HEADER_SIZE;
                hdrfree = hdrprev;
                hdrprev = hdrprev2;
            }
            if( hdrfree->next && hdrfree->next->type == XMEM_LIST_TYPE_FREE )
            {
                hdrfree->size += hdrfree->next->size + XMEM_HEADER_SIZE;
                hdrfree->next = hdrfree->next->next;
            }

            if( ( AddressType ) hdrfree + hdrfree->size + XMEM_HEADER_SIZE == xMemMgrHdrListEnd)
            {
                xMemMgrHdrListEnd -= hdrfree->size + XMEM_HEADER_SIZE;
                if( hdrprev ) hdrprev->next = NULL;
                else xMemMgrHdrList = NULL;
            }

            return;
        }

        hdrprev2 = hdrprev;
        hdrprev = hdrfree;
        hdrfree = hdrfree->next;
    }

    xMemAssert( 0 );
}

/**
 * @brief allocate a memory bock
 * @param  size             allocate memeory size
 * @return void* NULL-failure, other-memory address
 */
static void * xMemBlockAlloc( size_t size )
{
    void * ptr = NULL;
    pxMemBlock blkprev = NULL, blk = NULL, blknew = NULL, blkalloc = NULL;
    u16 allocsize, remainsize;

    /*
     -------------------------------------------
     |  ...  |  next  |  blk  |  prev  |  ...  |
     -------------------------------------------
    */

    blk = xMemBlkList;
    blkprev = xMemBlkList;
    remainsize = xMemBlkPoolStart - xMemMgrHdrListEnd;
    blkalloc = NULL;
    allocsize = XMEM_ALIGN( size, XMEM_ALIGNMENT_SIZE );

    #if XMEM_CORRUPT_CHECK
    allocsize += XMEM_BARRIER_SIZE;
    #endif// end of XMEM_CORRUPT_CHECK

    while( blk )
    {
        if( blk->free )
        {
           if( blk->blksize == allocsize )
           {//most fitable, block size equals to required size
                blk->free = 0;
                ptr = ( void* ) blk->addr;
                goto got_block;
           }
           else if( blk->blksize > allocsize && ( blk->blksize - allocsize ) < remainsize )
           {// find minimal fitable size block
                remainsize = blk->blksize-allocsize;
                blkalloc = blk;
           }
        }
        blkprev = blk;
        blk = blk->next;    
    }

    if( blkalloc )
    {
        if( remainsize >= XMEM_BALLANCE_SIZE )
        {
            //split into 2 blocks
            blknew = ( pxMemBlock ) xMemMgrHdrGet( XMEM_LIST_TYPE_BLOCK, XMEM_NODE_SIZE( xMemBlock ) );
            if( blknew != NULL )
            {
                blknew->blksize = remainsize;
                blknew->free = 1;
                blknew->next = blkalloc->next;
                blknew->addr = ( void * )( ( AddressType ) blkalloc->addr + allocsize );
                #if XMEM_CORRUPT_CHECK
                ( * ( AddressType * ) blknew->addr ) = XMEM_BARRIER_VALUE;
                #endif // end of XMEM_CORRUPT_CHECK
                blkalloc->next = blknew;
                blkalloc->blksize = allocsize;
            }
        }
        
        blkalloc->free = 0;
        ptr = (void*)blkalloc->addr;
        goto got_block;        
    }
    else if( remainsize > allocsize )
    {
        blknew=( pxMemBlock ) xMemMgrHdrGet ( XMEM_LIST_TYPE_BLOCK, XMEM_NODE_SIZE( xMemBlock ) );
        if( blknew != NULL )
        {
            if( blkprev )
            {
                blkprev->next = blknew;
            }
            else
            {
                xMemBlkList = blknew;
            }

            blknew->next = NULL;
            blknew->blksize = allocsize;
            blknew->free = 0;
            xMemBlkPoolStart -= allocsize;
            blknew->addr = ( void * ) xMemBlkPoolStart;
            blkalloc = blknew;
            ptr = ( void* ) blkalloc->addr;
            goto got_block;
        }
    }

    return NULL;

got_block:
    #if XMEM_CORRUPT_CHECK
    ( *( AddressType * )ptr ) = XMEM_BARRIER_VALUE;
    ptr = ( void * )( ( AddressType ) ptr + XMEM_BARRIER_SIZE );
    #endif // end of XMEM_CORRUPT_CHECK
    return ptr;
}

/**
 * @brief 
 * @param  ptr              pointer to free
 * @return u8 0-success,1-failure
 */
static u8 xMemBlockFree( void *ptr )
{
    pxMemBlock blkprev = NULL, blkfree = NULL, blkprev2 = NULL;

    /*
     -------------------------------------------
     |  ...  |  next  |  blk  |  prev  |  ...  |
     -------------------------------------------
    */

    if( ( AddressType ) ptr < XMEM_POOL_START || ( AddressType )ptr > XMEM_POOL_END)
        return 1;

    #if XMEM_CORRUPT_CHECK
    ptr = ( void * )( ( AddressType ) ptr - XMEM_BARRIER_SIZE );
    #endif // end of XMEM_CORRUPT_CHECK

    blkfree = xMemBlkList;
    while( blkfree )
    {
        if( blkfree->addr == ptr )
        {
            blkfree->free = 1;
            //may move this block of code to memory collection
            if( blkprev && blkprev->free )
            {
                blkprev->blksize += blkfree->blksize;
                blkprev->next = blkfree->next;
                blkprev->addr = blkfree->addr;
                xMemMgrHdrPut( blkfree );
                blkfree = blkprev;
                blkprev = blkprev2;
            }

            if( blkfree->addr == ( void * ) xMemBlkPoolStart )
            {
                xMemBlkPoolStart += blkfree->blksize;
                if( blkprev )
                {
                    blkprev->next = blkfree->next;
                }
                else
                {
                    blkfree->addr = NULL;
                    blkfree->blksize = 0;
                    blkfree->next = NULL;
                    xMemBlkList = NULL;
                }
                xMemMgrHdrPut( blkfree );
            }
            else  if( blkfree->next && blkfree->next->free )
            {
                blkprev = blkfree;
                blkfree = blkfree->next;

                blkprev->blksize += blkfree->blksize;
                blkprev->addr = blkfree->addr;
                blkprev->next = blkfree->next;
                xMemMgrHdrPut( blkfree );
            }
            //end
            return 0;
        }
        blkprev2 = blkprev;
        blkprev = blkfree;
        blkfree = blkfree->next;
    }

    return 1;
}

#if XMEM_CORRUPT_CHECK
/**
 * @brief corrupt check
 */
void xMemCorruptCheck( void )
{
    pxMemMgrHdr hdr, prehdr ;
    pxMemBlock pmemblk, preblk;

    prehdr = hdr = xMemMgrHdrList;
    while( hdr )
    {
        if( hdr->type >= XMEM_LIST_TYPE_MAX )
        {
            xMemInfoPrintf(RAMADDR_PRINTF_XFMT "error hdr type:%02x, size:%04x, next:" RAMADDR_PRINTF_XFMT "\r\n",
                            ( AddressType ) hdr,hdr->type,hdr->size,( AddressType ) hdr->next );
            xMemDump("corrupt", ( unsigned char * )XMEM_POOL_START, ( ( AddressType ) hdr ) - XMEM_POOL_START );
            xMemDump("corrupt", ( unsigned char * )( ( void * ) hdr ), 128 );
            xMemAssert( 0 );
        }
        prehdr = hdr;
        hdr = hdr->next;
    }

    preblk = pmemblk = xMemBlkList;
    while( pmemblk )
    {
        if( *( ( AddressType * ) pmemblk->addr ) != XMEM_BARRIER_VALUE )
        {
            xMemInfoPrintf("block: "  RAMADDR_PRINTF_XFMT " address: " RAMADDR_PRINTF_XFMT "\r\n",
                            ( AddressType ) pmemblk, ( ( AddressType ) pmemblk->addr ) );
            xMemDump("corrupt", ( unsigned char *) preblk->addr, preblk->blksize );
            xMemDump("corrupt", (unsigned char *) pmemblk->addr, pmemblk->blksize );
            xMemAssert(0);
        }
        preblk=pmemblk;
        pmemblk=pmemblk->next;
    }
}
#endif // end of XMEM_CORRUPT_CHECK

#else

/**
 * @brief allocate a memory bock
 * @param  size             allocate memeory size
 * @return void* NULL-failure, other-memory address
 */
static void * xMemBlockAlloc( size_t size )
{
    pxMemBlock blkprev = NULL, blk = NULL, blknew = NULL, blkalloc = NULL;
    u16 allocsize, remainsize;

    /*
     --------------------------------------------------------------
     |       |     prev     |     blk      |    next      |       |
     |  ...  |--------------|--------------|--------------|  ...  |
     |       |header|  mem  |header|  mem  |header|  mem  |       |
     --------------------------------------------------------------
    */

    blk = xMemBlkList;
    remainsize = xMem_Size;
    blkalloc = NULL;
    allocsize = XMEM_ALIGN( size, XMEM_ALIGNMENT_SIZE );

    while( blk )
    {
        if( blk->free )
        {
           if( blk->blksize == allocsize )
           {//most fitable, block size equals to required size
               blk->free = 0;
               return ( void * )( ( AddressType ) blk + XMEM_BLOCK_SIZE );
           }
           else if(blk->blksize>allocsize && ( blk->blksize - allocsize ) < remainsize)
           {// find minimal fitable size block
                remainsize = blk->blksize - allocsize;
                blkalloc = blk;
           }
        }
        blkprev = blk;
        blk = blk->next;
    }

    if( blkalloc )
    {
        if( remainsize > ( XMEM_BLOCK_SIZE + XMEM_BALLANCE_SIZE ) )
        {
            //split into 2 blocks
            blknew = ( pxMemBlock )( ( void * )( ( AddressType ) blkalloc + allocsize + XMEM_BLOCK_SIZE ) );
            blknew->blksize = remainsize-XMEM_BLOCK_SIZE;
            blknew->free = 1;
            blknew->next = blkalloc->next;
            blkalloc->next = blknew;
            blkalloc->blksize = allocsize;
        }

        blkalloc->free = 0;
        return ( void * )( ( AddressType ) blkalloc + XMEM_BLOCK_SIZE );
    }

    #if XMEM_CORRUPT_CHECK
    xMemCorruptCheck();
    #endif //end of XMEM_CORRUPT_CHECK
    return NULL;
}

/**
 * @brief 
 * @param  ptr              pointer to free
 * @return u8 0-success,1-failure
 */
static u8 xMemBlockFree( void *ptr ){
    pxMemBlock blkprev = NULL, blkfree = NULL;

    /*
     --------------------------------------------------------------
     |       |     prev     |     blk      |    next      |       |
     |  ...  |--------------|--------------|--------------|  ...  |
     |       |header|  mem  |header|  mem  |header|  mem  |       |
     --------------------------------------------------------------
    */

    blkfree = xMemBlkList;
    while( blkfree )
    {
        if( ( AddressType ) blkfree + XMEM_BLOCK_SIZE == ( AddressType ) ptr )
        {
            blkfree->free = 1;
            //merge physical neighbor blocks, previous or next, assure block will not overlap reserve space
            if( blkprev && blkprev->free )
            {
                blkprev->blksize += ( blkfree->blksize + XMEM_BLOCK_SIZE );
                blkprev->next = blkfree->next;
                blkfree = blkprev;
            }

            if( blkfree->next && blkfree->next->free )
            {
                blkfree->blksize += ( blkfree->next->blksize + XMEM_BLOCK_SIZE );
                blkfree->next = blkfree->next->next;
            }

            return 0;
        }

        blkprev = blkfree;
        blkfree = blkfree->next;
    }

    return 1;
}

#if XMEM_CORRUPT_CHECK
/**
 * @brief corrupt check
 */
void xMemCorruptCheck(void)
{
    pxMemBlock pmemblk, preblk;

    preblk = pmemblk = xMemBlkList;
    while( pmemblk )
    {
        if( pmemblk->free > 1
            || ( pmemblk->next &&
                    ( ( AddressType ) pmemblk + XMEM_BLOCK_SIZE + pmemblk->blksize != (AddressType) pmemblk->next
                    || ( AddressType ) pmemblk->next >= XMEM_POOL_END
                    || ( AddressType ) pmemblk->next <= XMEM_POOL_START )
                )
           )
        {
            xMemInfoPrintf( "blk:" RAMADDR_PRINTF_XFMT ",blksize:%04x,blknext:" RAMADDR_PRINTF_XFMT ",free:%02x\r\n",
                        ( AddressType ) pmemblk, pmemblk->blksize, ( AddressType ) pmemblk->next, pmemblk->free );
            xMemDump("corrupt", ( unsigned char * )preblk, preblk->blksize + XMEM_BLOCK_SIZE);
            xMemDump("corrupt", ( unsigned char * )pmemblk, 128);
            xMemAssert( 0 );
        }
        preblk = pmemblk;
        pmemblk = pmemblk->next;
    }
}
#endif // end of XMEM_CORRUPT_CHECK

#endif // end of XMEM_HEADER_DIVIDE

#if XMEM_SUPERBLOCK_SUPPORT
/**
 * @brief Init a super block
 * @param  psuperblock      pointer to a super block
 * @param  addr             memory address
 * @param  ncell             number of cells
 * @param  cellsize          cell size
 */
static void xMemSuperBlockInit ( xMemSuperBlock * psuperblock, void *addr, u8 ncell, u16 cellsize )
{  
    int i;

    if ( psuperblock == NULL || addr == NULL || ncell < 2 || cellsize < sizeof( void * ) )
    {
        xMemDebugPrintf("Init Super Block [Failed], super block:" RAMADDR_PRINTF_XFMT ", address:" RAMADDR_PRINTF_XFMT ", blocks:%02x,block size:%4x\r\n",
                    ( AddressType ) psuperblock, ( AddressType )addr, ncell, cellsize );
        return ;
    }

    psuperblock->addr = addr;
    psuperblock->cellsize = cellsize;
    psuperblock->nfree = ncell;
    psuperblock->ncell = ncell;
    psuperblock->next = NULL;

    i = 0;
    while( ncell ){
        if( ncell >= XMEM_SUPERBLOCK_CTRLBITS ){
            psuperblock->freeList[i] = XMEM_SUPERBLOCK_CTRLALL;
            ncell -= XMEM_SUPERBLOCK_CTRLBITS;
        } else {
            psuperblock->freeList[i] = ( ( 1 << ncell ) - 1 );
            ncell = 0;
            break;
        }
        i++;   
    }

    return ;
}

/**
 * @brief Append a new super block
 * @param  superblocklist   super block list
 * @return xMemSuperBlock* 
 */
static xMemSuperBlock * xMemSuperBlockAppend( xMemSuperBlock * superblocklist )
{
    xMemSuperBlock * pmemtail, *pmemnew = NULL;
    void *blk;

    pmemtail = superblocklist;
    while( pmemtail->next ) pmemtail = pmemtail->next;
    #if XMEM_HEADER_DIVIDE
    pmemnew = ( xMemSuperBlock * )xMemMgrHdrGet( XMEM_LIST_TYPE_SUPERBLOCK , XMEM_NODE_SIZE( xMemSuperBlock ) );
    #else
    pmemnew = ( xMemSuperBlock * )xMemBlockAlloc( XMEM_NODE_SIZE( xMemSuperBlock ) );
    #endif// end of XMEM_HEADER_DIVIDE
    if(pmemnew)
    {
        blk = xMemBlockAlloc( superblocklist->cellsize * ( superblocklist->ncell / 2 ) );
        if(blk)
        {
            xMemSuperBlockInit( pmemnew, blk, superblocklist->ncell / 2, superblocklist->cellsize );
            pmemtail->next = pmemnew;
        }
        else
        {
            #if XMEM_HEADER_DIVIDE
            xMemMgrHdrPut( pmemnew );
            #else
            xMemBlockFree( pmemnew );
            #endif // end of XMEM_HEADER_DIVIDE
            pmemnew = NULL;
        }
    }
    return pmemnew;
}

/**
 * @brief Init super block list
 */
static void xMemSuperBlockListInit(void)
{
    u32 size = 0;
    u8 * blk;
    int i, len;
    
    len = sizeof( xMemSuperBlockInitDescList ) / sizeof( xMemSuperBlockInitDesc );
    for( i = 0; i < len; i++ )
    {
        size += xMemSuperBlockInitDescList[i].cellsize * xMemSuperBlockInitDescList[i].ncell;
        if( xMemSuperBlockInitDescList[i].cellsize > xMemSuperBlkCellMax )
            xMemSuperBlkCellMax = xMemSuperBlockInitDescList[i].cellsize;
    }

    blk = xMemBlockAlloc(size);

    if(blk)
    {
        for( i = 0; i < len; i++ ){
            size = XMEM_ALIGN( xMemSuperBlockInitDescList[i].ncell, XMEM_SUPERBLOCK_CTRLBITS ) / 8;
            size += XMEM_NODE_SIZE( xMemSuperBlock );
            #if XMEM_HEADER_DIVIDE
            xMemSuperBlockList[i] = ( xMemSuperBlock * ) xMemMgrHdrGet( XMEM_LIST_TYPE_SUPERBLOCK , size );
            #else
            xMemSuperBlockList[i] = ( xMemSuperBlock * )xMemBlockAlloc( size );
            #endif // end of XMEM_HEADER_DIVIDE
            xMemSuperBlockInit(xMemSuperBlockList[i], blk, xMemSuperBlockInitDescList[i].ncell, xMemSuperBlockInitDescList[i].cellsize );
            blk += xMemSuperBlockInitDescList[i].cellsize * xMemSuperBlockInitDescList[i].ncell;
        }
    }
}

/**
 * @brief Get cell from a super block list
 * @param  superblocklist   super block list
 * @param  size             Cell size required
 * @return void*  NULL-failure, other-cell address
 */
static void * xMallocCellGet(xMemSuperBlock * superblocklist,size_t size)
{
    int i, j, group, num;
    void * pblk;
    xMemSuperBlock *pmemiter;

    if ( superblocklist == NULL || size > superblocklist->cellsize )    return NULL;

    pmemiter = superblocklist;

    while( pmemiter )
    {
        if ( pmemiter->nfree > 0)
        {
            break;
        }

        pmemiter = pmemiter->next;
    }

    if( pmemiter == NULL ) pmemiter = xMemSuperBlockAppend( superblocklist );

    group = ( pmemiter->ncell + ( XMEM_SUPERBLOCK_CTRLBITS - 1 )) / XMEM_SUPERBLOCK_CTRLBITS;

    if( pmemiter )
    {
        for( i = 0; i < group; i++ )
        {
            num = pmemiter->ncell - i * XMEM_SUPERBLOCK_CTRLBITS;
            if( num > XMEM_SUPERBLOCK_CTRLBITS ){
                num = XMEM_SUPERBLOCK_CTRLBITS;
            }

            for( j = 0; j < num; j++ )
            {
                if( ( 1 << j ) & ( pmemiter->freeList[i] ) )
                {
                    pmemiter->freeList[i] &= ( ~ ( 1 << j ) );
                    pblk = ( void * )( ( AddressType ) pmemiter->addr + ( i * XMEM_SUPERBLOCK_CTRLBITS+j ) * ( AddressType )( pmemiter->cellsize ) );
                    pmemiter->nfree--;
                    return ( pblk );
                }
            }
        }
    }

    return NULL;
}

/**
 * @brief  put cell to a super block list
 * @param  superblocklist   super block list
 * @param  pblk             cell to put
 */
static void  xMallocCellPut ( xMemSuperBlock  *superblocklist, void *pblk )
{
    int index;

    if (superblocklist == NULL || pblk == NULL || superblocklist->nfree >= superblocklist->ncell )  return ;

    index = ( ( AddressType ) pblk - ( AddressType ) superblocklist->addr ) / superblocklist->cellsize;

    if( !( superblocklist->freeList[index/XMEM_SUPERBLOCK_CTRLBITS] & ( 1 << ( index % XMEM_SUPERBLOCK_CTRLBITS ) ) ) ){
        superblocklist->freeList[index/XMEM_SUPERBLOCK_CTRLBITS] |= ( 1 << ( index % XMEM_SUPERBLOCK_CTRLBITS ) );
        superblocklist->nfree++;
    }

    return;
}

/**
 * @brief Allocate a block of memory from super blocks
 * @param  size             memory size required
 * @return void* NULL-failure, other-memory address
 */
static void * xMallocCellAlloc(size_t size)
{
    int i;
    void * ptr = NULL;

    for(i = 0 ; i< sizeof( xMemSuperBlockList ) / sizeof( xMemSuperBlock * ); i++ )
    {
        if( size <= xMemSuperBlockList[i]->cellsize )
        {
            ptr = xMallocCellGet(xMemSuperBlockList[i], size);
            break;
        }
    }

    return ptr;
}

/**
 * @brief free a block of memory to super block list
 * @param  pblk             My Param doc
 * @return u8 0-success, 1-failure
 */
static u8 xMemCellFree(void * pblk)
{
    int i;
    u32 start, end, p;
    xMemSuperBlock  * pmem, * pmemprev = NULL;

    if (pblk == NULL)   return 0;

    for( i = 0 ; i < sizeof( xMemSuperBlockList ) / sizeof( xMemSuperBlock * ); i++ )
    {
        pmem = xMemSuperBlockList[i];
        while( pmem )
        {
            p = ( AddressType ) pblk;
            start = ( AddressType ) pmem->addr;
            end = start + pmem->cellsize * pmem->ncell;
            if( p >= start && p < end )
            {
                xMallocCellPut(pmem, pblk);
                if( pmem->nfree == pmem->ncell && pmemprev )
                {
                    pmemprev->next = pmem->next;
                    xMemBlockFree( pmem->addr );
                    xMemBlockFree( pmem );
                }
                return 0;
            }
            pmemprev = pmem;
            pmem = pmem->next;        
        }
    }
    return 1;
}
#endif // end of XMEM_SUPERBLOCK_SUPPORT

static u8 xmem_init_flag = 0;

/**
 * @brief Init X-Memory Pool
 * @param  addr             memory pool address
 * @param  size             memeory pool size in bytes
 */
void xMemInit( AddressType addr , size_t size )
{
    xMemDebugPrintf( "xMem Version: %s\r\n", XMEM_VER );
    xMem_Addr = addr;
    xMem_Size = size;

    #if XMEM_HEADER_DIVIDE
    xMemMgrHdrListInit();
    #endif// end of XMEM_HEADER_DIVIDE

    xMemBlockListInit();

    #if XMEM_SUPERBLOCK_SUPPORT
    xMemSuperBlockListInit();
    #endif // end of XMEM_SUPERBLOCK_SUPPORT

    xmem_init_flag=1;
}

/**
 * @brief allocate a block of memory
 * @param  size             memory size required
 * @return void* 
 */
void * xmalloc( size_t size )
{
    void * ptr = NULL;
    xMemAssert( xmem_init_flag == 1 );
    XMEM_ENTER_CRITICAL();

    #if XMEM_CORRUPT_CHECK
    xMemCorruptCheck();
    #endif // end of XMEM_CORRUPT_CHECK

    #if XMEM_SUPERBLOCK_SUPPORT
    if(size <= xMemSuperBlkCellMax)
    {
        ptr = xMallocCellAlloc( size );
    }
    if( ptr == NULL)
    #endif // end of XMEM_SUPERBLOCK_SUPPORT
    {
        ptr = xMemBlockAlloc( size );
    }

    XMEM_EXIT_CRITICAL();

    return ptr;
}

/**
 * @brief free a block of memory
 * @param  ptr              pointer to a block  of memory to be free
 */
void xfree( void *ptr )
{
    XMEM_ENTER_CRITICAL();

    #if XMEM_CORRUPT_CHECK
    xMemCorruptCheck();
    #endif // end of XMEM_CORRUPT_CHECK

    if(
        #if XMEM_SUPERBLOCK_SUPPORT
        xMemCellFree( ptr )&&
        #endif // end of XMEM_SUPERBLOCK_SUPPORT
        xMemBlockFree( ptr ) )
    {//Cell block first, then common block, avoid super block start addr equals common block start addr
        xMemDebugPrintf( "ptr:" RAMADDR_PRINTF_XFMT "\r\n", ( AddressType ) ptr );
        xMemBlockListInfoDump( xMemBlkList );

        #if XMEM_SUPERBLOCK_SUPPORT
        xMemSuperBlockInfoDump( xMemSuperBlockList, sizeof( xMemSuperBlockList ) / sizeof( xMemSuperBlock * ) );
        #endif // end of XMEM_SUPERBLOCK_SUPPORT
    }

    XMEM_EXIT_CRITICAL();
}

/**
 * @brief dump memory information
 */
void xMemInfoDump(void)
{
    #if XMEM_HEADER_DIVIDE
    xMemDebugPrintf("hdr end:" RAMADDR_PRINTF_XFMT ",blk start:" RAMADDR_PRINTF_XFMT "\r\n", xMemMgrHdrListEnd, xMemBlkPoolStart);
    xMemMgrHdrListInfoDump( xMemMgrHdrList );
    #endif // end of XMEM_HEADER_DIVIDE

    xMemBlockListInfoDump( xMemBlkList );

    #if XMEM_SUPERBLOCK_SUPPORT
    xMemSuperBlockInfoDump( xMemSuperBlockList, sizeof( xMemSuperBlockList ) / sizeof( xMemSuperBlock * ) );
    #endif // end of XMEM_SUPERBLOCK_SUPPORT

    xMemDebugPrintf( "\r\n" );
}
